package tree;

import javax.xml.bind.annotation.XmlID;
import java.util.Stack;

/**
 * 给你一个树，请你 按中序遍历 重新排列树，
 * 使树中最左边的结点现在是树的根，并且每个结点没有左子结点，
 * 只有一个右子结点。
 * @author le
 */
public class IncreasingOrderSearchTree
{
    static Stack<Integer>  stack = new Stack<>();

    public TreeNode increasingBST(TreeNode root) {

        if (root == null){
            return null;
        }
        midSearch(root);

        TreeNode head = new TreeNode(stack.pop());
        TreeNode pre = head;

        while(!stack.isEmpty()){
            TreeNode tmp = new TreeNode(stack.pop());
            pre.right = tmp;
            pre = pre.right;
        }

        return head;
    }

    public static void midSearch(TreeNode root){
        if (root != null){
            midSearch(root.right);

            System.out.println(root.val);
            stack.add(root.val);
            midSearch(root.left);
        }
    }

}
